package 算法;

public class Element {

    /**
     * 1、递归打印数字1-9
     * @param n
     */
    public void func(int n) {
        if(n>1){
            func(n-1);
        }
        System.out.println(n);
    }

    /**
     * 2、递归求和1-10
     * @param n
     * @return
     */
    public int sums(int start,int n) {
        if (n==start){
            return start;
        }
        return n+sums(start,n-1);
    }


    /**
     * 3、移除元素
     * @param nums
     * @param val
     * @return
     */
        public int removeElement(int[] nums,int val){
            int left=0;
            for (int right=0;right<nums.length;right++){
                if (nums[right]!=val){
                    nums[left]=nums[right];
                    left++;
                }
            }
            return left;
        }

    /**
     * 4、反转字符串
     * @param s
     */
        public void reverseString(char[] s){
            for (int i=0;i<s.length/2;i++){
                char temp=s[i];
                s[i]=s[s.length-i-1];
                s[s.length-i-1]=temp;
            }
        }

    /**
     * 5、爬楼梯
     * @param n
     * @return
     */
        public int climbStairs(int n){
            if(n<=1){
                return 1;
            }
            int[] res=new int[n+1];
            res[1]=1;
            res[2]=2;
            for (int i=3;i<n+1;i++){
                res[i]=res[i-1]+res[i-2];
            }
            return res[n];
        }

    /**
     * 6、最小花费爬楼梯
     * @param cost
     * @return
     */
        public int minCostClimbingStairs(int[] cost) {
            int n = cost.length;
            int[] dp = new int[n + 1];
            dp[0] = dp[1] = 0;
            for (int i = 2; i <n+1; i++) {
                dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
            }
            return dp[n];
        }

    /**
     * 7、门牌所需字符数量
     * @return
     */
        public int sumString(){
            int sum=0;
            for (int i=1;i<2020;i++){
                int res=i;
                while(res!=0){
                    if(res%10==2){
                        sum++;
                    }
                    res/=10;
                }
            }
            return sum;
        }

    /**
     * 8.1、将一个整数分解成3个正整数之和
     * @return
     */
        public int split(){
            int ans=0;
            for (int i=1;i<=2019;i++){
                for (int j=i+1;j<=2019;j++){
                    int k=2019-i-j;
                    if(this._check(i)&&this._check(j)&&this._check(k)&&i<j&&j<k) ans++;
                }
            }
            return ans;

        }

    /**
     * 8.2、验证该整数是否不包含数字2和4
     * @param x
     * @return
     */
        private boolean _check(int x){
            while(x!=0){
                int now=x%10;
                if(now==2||now==4) return false;
                x/=10;
            }
            return true;
        }


    /**
     * 动态规划解题步骤：
     * 1、确定dp数组以及下标含义
     * 2、确定递推公式
     * 3、dp数组如何初始化
     * 4、确定遍历顺序
     * 5、举例推导dp数组
     */

    /**
     * 回溯函数模板返回值以及参数
     * 回溯函数终止条件
     * 回溯搜索遍历过程
     */

//        void back(参数){
//            if(终止条件){
//                存放结果;
//                return;
//
//            }
//            for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
//                处理节点;
//                back(路径，选择列表);//递归
//                回溯，撤销处理结果
//            }
//        }

}
